package main

import (
	"fmt"
	"sort"
)

func main() {
	//nums := []int{0,2,1,-3}
	//i := threeSumClosest(nums, 1)

	nums := []int{1,1,1,1}
	i := threeSumClosest(nums, 3)
	fmt.Println(i)
}

func threeSumClosest(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}

	sort.Ints(nums)
	min := 1000000 // 最小差距
	result := 0
	for i := 0; i < len(nums); i++ {
		left, right := i+1, len(nums)-1

		for left < right {
			sum := nums[i] + nums[left] + nums[right]

			intervalAbs, interval := getInterval(target, sum)
			if intervalAbs < min {
				min = intervalAbs
				result = sum
			}else if interval > 0 {
				right--
			} else if interval < 0 {
				left++
			}else {
				left++
				right--
			}
		}
	}
	return result
}

func getInterval(target, sum int) (int, int) {
	v := sum - target
	if v < 0 {
		return -v, v
	} else {
		return v, v
	}
}
